Many forms of network activity create large volumes of streaming data. Various data domains such as chemical data, biological data and the web are structured as graphs. In streaming applications, these graphs are pushed to servers that process such information as a stream. These graph streams may include nodes and edges. For example, in a web graph, the nodes may correspond to URL addresses and the edges may correspond to links between URL addresses.
Graph streams arise in the context of a wide variety of social, information and communication network scenarios, in some of which the nodes are labeled. In such social, information and communication networks, it is often desirable to track interesting properties of the underlying nodes as they change over time. These dynamic properties can often be represented in the form of time-dependent labels associated with the nodes. Dynamic or sudden changes in such node labels may be indicative of important events or patterns of activity. However, tracking these dynamic or sudden changes can be challenging. Existing methods tend to be designed for the classification of static graphs, rather than for the detection of changes and anomalies in dynamic graph streams.